bluuebunny/crossref_metadata_2025 huggingface dataset:
A Spatially Sensitive Kernel to Predict Cognitive Performance from Short-Term Changes in Neural Structure
Authors: Ansari M. Hidayath , Coen Michael , Bendlin Barbara , Sager Mark , Johnson Sterling
Published: June 2022

This paper introduces a novel framework for performing machine learning onlongitudinal neuroimaging datasets. These datasets are characterized by theirsize, particularly their width (millions of features per data input). Specifically, we address the problem of detecting subtle, short-term changes inneural structure that are indicative of cognitive change and correlate withrisk factors for Alzheimer's disease. We introduce a new spatially-sensitivekernel that allows us to reason about individuals, as opposed to populations. In doing so, this paper presents the first evidence demonstrating that verysmall changes in white matter structure over a two year period can predictchange in cognitive function in healthy adults.
Joint Morphological Generation and Syntactic Linearization
Authors: Song Linfeng , Zhang Yue , Song Kai , Liu Qun
Published: June 2022

There has been growing interest in stochastic methods to natural language generation (NLG). While most NLG pipelines separate morphological generation and syntactic linearization, the two tasks are closely related. In this paper, we study joint morphological generation and linearization, making use of word order and inflections information for both tasks and reducing error propagation. Experiments show that the joint method significantly outperforms a strong pipelined baseline (by 1.1 BLEU points). It also achieves the best reported result on the Generation Challenge 2011 shared task.
Mind the Gap: Machine Translation by Minimizing the Semantic Gap in Embedding Space
Authors: Zhang Jiajun , Liu Shujie , Li Mu , Zhou Ming , Zong Chengqing
Published: June 2022

The conventional statistical machine translation (SMT) methods perform the decoding process by compositing a set of the translation rules which are associated with high probabilities. However, the probabilities of the translation rules are calculated only according to the cooccurrence statistics in the bilingual corpus rather than the semantic meaning similarity. In this paper, we propose a Recursive Neural Network (RNN) based model that converts each translation rule into a compact real-valued vector in the semantic embedding space and performs the decoding process by minimizing the semantic gap between the source language string and its translation candidates at each state in a bottom-up structure. The RNN-based translation model is trained using a max-margin objective function. Extensive experiments on Chinese-to-English translation show that our RNN-based model can significantly improve the translation quality by up to 1.68 BLEU score.
Chinese Overt Pronoun Resolution: A Bilingual Approach
Authors: Chen Chen , Ng Vincent
Published: June 2022

Much research has been done on the problem of English pronoun resolution, but there has been relatively little work on the corresponding problem of Chinese pronoun resolution. While pronoun resolution in both languages remains a challenging task, Chinese pronoun resolution is further complicated by (1) the lack of publicly available Chinese word lists or dictionaries that can be used to look up essential mention attributes such as gender and number; and (2) the relative dearth of Chinese coreference-annotated data. Existing approaches to Chinese pronoun resolution are monolingual, training and testing a pronoun resolver on Chinese data. In contrast, we propose a bilingual approach to Chinese pronoun resolution, aiming to improve the resolution of Chinese pronouns by leveraging the publicly available English dictionaries and coreference annotations. Experiments on the OntoNotes 5.0 corpus demonstrate that our bilingual approach to Chinese pronoun resolution significantly surpasses the performance of state-of-the-art monolingual approaches.
Chinese Zero Pronoun Resolution: An Unsupervised Approach Combining Ranking and Integer Linear Programming
Authors: Chen Chen , Ng Vincent
Published: June 2022

State-of-the-art approaches to Chinese zero pronoun resolution are supervised, requiring training documents with manually resolved zero pronouns. To eliminate the reliance on annotated data, we propose an unsupervised approach to this task. Underlying our approach is the novel idea of employing a model trained on manually resolved overt pronouns to resolve zero pronouns. Experimental results on the OntoNotes 5.0 corpus are encouraging: our unsupervised model surpasses its supervised counterparts in performance.
Echo-State Conditional Restricted Boltzmann Machines
Authors: Chatzis Sotirios
Published: June 2022

Restricted Boltzmann machines (RBMs) are a powerful generative modeling technique, based on a complex graphical model of hidden (latent) variables. Conditional RBMs (CRBMs) are an extension of RBMs tailored to modeling temporal data. A drawback of CRBMs is their consideration of linear temporal dependencies, which limits their capability to capture complex temporal structure. They also require many variables to model long temporal dependencies, a fact that might provoke overfitting proneness. To resolve these issues, in this paper we propose the echo-state CRBM (ES-CRBM): our model uses an echo-state network reservoir in the context of CRBMs to efficiently capture long and complex temporal dynamics, with much fewer trainable parameters compared to conventional CRBMs. In addition, we introduce an (implicit) mixture of ES-CRBM experts (im-ES-CRBM) to enhance even further the capabilities of our ES-CRBM model. The introduced im-ES-CRBM allows for better modeling temporal observations which might comprise a number of latent or observable subpatterns that alternate in a dynamic fashion. It also allows for performing sequence segmentation using our framework. We apply our methods to sequential data modeling and classification experiments using public datasets. As we show, our approach outperforms both existing RBM-based approaches as well as related state-of-the-art methods, such as conditional random fields.
Dynamic Bayesian Probabilistic Matrix Factorization
Authors: Chatzis Sotirios
Published: June 2022

Collaborative filtering algorithms generally rely on the assumption that user preference patterns remain stationary. However, real-world relational data are seldom stationary. User preference patterns may change over time, giving rise to the requirement of designing collaborative filtering systems capable of detecting and adapting to preference pattern shifts. Motivated by this observation, in this paper we propose a dynamic Bayesian probabilistic matrix factorization model, designed for modeling time-varying distributions. Formulation of our model is based on imposition of a dynamic hierarchical Dirichlet process (dHDP) prior over the space of probabilistic matrix factorization models to capture the time-evolving statistical properties of modeled sequential relational datasets. We develop a simple Markov Chain Monte Carlo sampler to perform inference. We present experimental results to demonstrate the superiority of our temporal model.
Improving Semi-Supervised Target Alignment via Label-Aware Base Kernels
Authors: Wang Qiaojun , Zhang Kai , Jiang Guofei , Maric Ivan
Published: June 2022

Semi-supervised kernel design is an essential step for obtaining good predictive performance in semi-supervised learning tasks. In the current literatures, a large family of algorithms builds the new kernel by using the weighted average of predefined base kernels. While optimal weighting schemes have been studied extensively, the choice of base kernels received much less attention. Many methods simply adopt the empirical kernel matrices or its eigenvectors. Such base kernels are computed irrespective of class labels and may not always reflect useful structures in the data. As a result, in case of poor base kernels, the generalization performance can be degraded however hard their weights are tuned. In this paper, we propose to construct high-quality base kernels with the help of label information to globally improve the final target alignment. In particular, we devise label-aware kernel eigenvectors under the framework of semi-supervised eigenfunction extrapolation, which span base kernels that are more useful for learning. Such base kernels are individually better aligned to the learning target, so their mixture will more likely generate a good classifier. Our approach is computationally efficient, and demonstrates encouraging performance in semi-supervised classification and regression.
Optimal Neighborhood Preserving Visualization by Maximum Satisfiability
Authors: Bunte Kerstin , Järvisalo Matti , Berg Jeremias , Myllymäki Petri , Peltonen Jaakko , Kaski Samuel
Published: June 2022

We present a novel approach to low-dimensional neighbor embedding for visualization, based on formulating an information retrieval based neighborhood preservation cost function as Maximum satisfiability on a discretized output display. The method has a rigorous interpretation as optimal visualization based on the cost function. Unlike previous low-dimensional neighbor embedding methods, our formulation is guaranteed to yield globally optimal visualizations, and does so reasonably fast. Unlike previous manifold learning methods yielding global optima of their cost functions, our cost function and method are designed for low-dimensional visualization where evaluation and minimization of visualization errors are crucial. Our method performs well in experiments, yielding clean embeddings of datasets where a state-of-the-art comparison method yields poor arrangements. In a real-world case study for semi-supervised WLAN signal mapping in buildings we outperform state-of-the-art methods.
Convex Co-embedding
Authors: Mirzazadeh Farzaneh , Guo Yuhong , Schuurmans Dale
Published: June 2022

We present a general framework for association learning, where entities are embedded in a common latent space to express relatedness by geometry -- an approach that underlies the state of the art for link prediction, relation learning, multi-label tagging, relevance retrieval and ranking. Although current approaches rely on local training applied to non-convex formulations, we demonstrate how general convex formulations can be achieved for entity embedding, both for standard multi-linear and prototype-distance models. We investigate an efficient optimization strategy that allows scaling. An experimental evaluation reveals the advantages of global training in different case studies.
Online and Stochastic Learning with a Human Cognitive Bias
Authors: Oiwa Hidekazu , Nakagawa Hiroshi
Published: June 2022

Sequential learning for classification tasks is an effective tool in the machine learning community. In sequential learning settings, algorithms sometimes make incorrect predictions on data that were correctly classified in the past. This paper explicitly deals with such inconsistent prediction behavior. Our main contributions are 1) to experimentally show its effect for user utilities as a human cognitive bias, 2) to formalize a new framework by internalizing this bias into the optimization problem, 3) to develop new algorithms without memorization of the past prediction history, and 4) to show some theoretical guarantees of our derived algorithm for both online and stochastic learning settings. Our experimental results show the superiority of the derived algorithm for problems involving human cognition.
Locality Preserving Projection for Domain Adaptation with Multi-Objective Learning
Authors: Shu Le , Ma Tianyang , Latecki Longin Jan
Published: June 2022

In many practical cases, we need to generalize a model trained in a source domain to a new target domain.However, the distribution of these two domains may differ very significantly, especially sometimes some crucial target features may not have support in the source domain.This paper proposes a novel locality preserving projection method for domain adaptation task,which can find a linear mapping preserving the 'intrinsic structure' for both source and target domains.We first construct two graphs encoding the neighborhood information for source and target domains separately.We then find linear projection coefficients which have the property of locality preserving for each graph.Instead of combing the two objective terms under compatibility assumption and requiring the user to decide the importance of each objective function,we propose a multi-objective formulation for this problem and solve it simultaneously using Pareto optimization.The Pareto frontier captures all possible good linear projection coefficients that are preferred by one or more objectives.The effectiveness of our approach is justified by both theoretical analysis and empirical results on real world data sets.The new feature representation shows better prediction accuracy as our experiments demonstrate.
Learning Relative Similarity by Stochastic Dual Coordinate Ascent
Authors: Wu Pengcheng , Ding Yi , Zhao Peilin , Miao Chunyan , Hoi Steven
Published: June 2022

Learning relative similarity from pairwise instances is an important problem in machine learning and has a wide range of applications. Despite being studied for years, some existing methods solved by Stochastic Gradient Descent (SGD) techniques generally suffer from slow convergence. In this paper, we investigate the application of Stochastic Dual Coordinate Ascent (SDCA) technique to tackle the optimization task of relative similarity learning by extending from vector to matrix parameters. Theoretically, we prove the optimal linear convergence rate for the proposed SDCA algorithm, beating the well-known sublinear convergence rate by the previous best metric learning algorithms. Empirically, we conduct extensive experiments on both standard and large-scale data sets to validate the effectiveness of the proposed algorithm for retrieval tasks.
Large-Scale Optimistic Adaptive Submodularity
Authors: Gabillon Victor , Kveton Branislav , Wen Zheng , Eriksson Brian , Muthukrishnan S.
Published: June 2022

Maximization of submodular functions has wide applications in artificial intelligence and machine learning. In this paper, we propose a scalable learning algorithm for maximizing an adaptive submodular function. The key structural assumption in our solution is that the state of each item is distributed according to a generalized linear model, which is conditioned on the feature vector of the item. Our objective is to learn the parameters of this model. We analyze the performance of our algorithm, and show that its regret is polylogarithmic in time and linear in the number of features. Finally, we evaluate our solution on two problems, preference elicitation and adaptive face detection, and demonstrate that high-quality policies can be learned sample efficiently.
Evolutionary Dynamics of Q-Learning over the Sequence Form
Authors: Panozzo Fabio , Gatti Nicola , Restelli Marcello
Published: June 2022

Multi-agent learning is a challenging open task in artificial intelligence. It is known an interesting connection between multi-agent learning algorithms and evolutionary game theory, showing that the learning dynamics of some algorithms can be modeled as replicator dynamics with a mutation term. Inspired by the recent sequence-form replicator dynamics, we develop a new version of the Q-learning algorithm working on the sequence form of an extensive-form game allowing thus an exponential reduction of the dynamics length w.r.t. those of the normal form. The dynamics of the proposed algorithm can be modeled by using the sequence-form replicator dynamics with a mutation term. We show that, although sequence-form and normal-form replicator dynamics are realization equivalent, the Q-learning algorithm applied to the two forms have non-realization equivalent dynamics. Originally from the previous works on evolutionary game theory models form multi-agent learning, we produce an experimental evaluation to show the accuracy of the model.
Mixing-Time Regularized Policy Gradient
Authors: Morimura Tetsuro , Osogami Takayuki , Shirai Tomoyuki
Published: June 2022

Policy gradient reinforcement learning (PGRL) has been receiving substantial attention as a mean for seeking stochastic policies that maximize cumulative reward. However, the learning speed of PGRL is known to decrease substantially when PGRL explores the policies that give the Markov chains having long mixing time. We study a new approach of regularizing how the PGRL explores the policies by the use of the hitting time of the Markov chains. The hitting time gives an upper bound on the mixing time, and the proposed approach improves the learning efficiency by keeping the mixing time of the Markov chains short. In particular, we propose a method of temporal-difference learning for estimating the gradient of the hitting time. Numerical experiments show that the proposed method outperforms conventional methods of PGRL.
Robust Non-Negative Dictionary Learning
Authors: Pan Qihe , Kong Deguang , Ding Chris , Luo Bin
Published: June 2022

Dictionary learning plays an important role in machine learning, where data vectors are modeled as a sparse linear combinations of basis factors (i.e., dictionary). However, how to conduct dictionary learning in noisy environment has not been well studied. Moreover, in practice, the dictionary (i.e., the lower rank approximation of the data matrix) and the sparse representations are required to be nonnegative, such as applications for image annotation, document summarization, microarray analysis. In this paper, we propose a new formulation for non-negative dictionary learning in noisy environment, where structure sparsity is enforced on sparse representation. The proposed new formulation is also robust for data with noises and outliers, due to a robust loss function used. We derive an efficient multiplicative updating algorithm to solve the optimization problem, where dictionary and sparse representation are updated iteratively. We prove the convergence and correctness of proposed algorithm rigorously.We show the differences of dictionary at different level of sparsity constraint.The proposed algorithm can be adapted for clustering and semi-supervised learning.
On Boosting Sparse Parities
Authors: Reyzin Lev
Published: June 2022

While boosting has been extensively studied, considerablyless attention has been devoted to the task of designing good weaklearning algorithms. In this paper we consider the problem of designing weak learners thatare especially adept to the boosting procedure and specifically the AdaBoost algorithm. First we describe conditions desirable for a weak learning algorithm. We then propose using sparse parity functions as weak learners, which have many of our desired properties, as weak learners in boosting. Our experimental tests show the proposed weak learners tobe competitive with the most widely used ones: decisionstumps and pruned decision trees.
HC-Search for Multi-Label Prediction: An Empirical Study
Authors: Doppa Janardhan Rao , Yu Jun , Ma Chao , Fern Alan , Tadepalli Prasad
Published: June 2022

Multi-label learning concerns learning multiple, overlapping, and correlated classes. In this paper, we adapt a recent structured prediction framework called HC-Search for multi-label prediction problems. One of the main advantages of this framework is that its training is sensitive to the loss function, unlike the other multi-label approaches that either assume a specific loss function or require a manual adaptation to each loss function. We empirically evaluate our instantiation of the HC-Search framework along with many existing multi-label learning algorithms on a variety of benchmarks by employing diverse task loss functions. Our results demonstrate that the performance of existing algorithms tends to be very similar in most cases, and that the HC-Search approach is comparable and often better than all the other algorithms across different loss functions.
Efficiently Implementing GOLOG with Answer Set Programming
Authors: Ryan Malcolm
Published: June 2022

In this paper we investigate three different approaches to encoding domain-dependent control knowledge for Answer-Set Planning. Starting with a standard imple- mentation of the action description language B, we add control knowledge expressed in the GOLOG logic pro- gramming language. A naive encoding, following the original definitions of Levesque et al., is shown to scale poorly. We examine two alternative codings based on the transition semantics of ConGOLOG. We show that a speed increase of multiple orders of magnitude can be obtain by compiling the GOLOG program into a finite- state machine representation.
Saturated Path-Constrained MDP: Planning under Uncertainty and Deterministic Model-Checking Constraints
Authors: Sprauel Jonathan , Kolobov Andrey , Teichteil-Königsbuch Florent
Published: June 2022

In many probabilistic planning scenarios, a system’s behavior needs to not only maximize the expected utility but also obey certain restrictions. This paper presents Saturated Path-Constrained Markov Decision Processes (SPC MDPs), a new MDP type for planning under uncertainty with deterministic model-checking constraints, e.g., "state s must be visited befores s'", "the system must end up in s", or "the system must never enter s". We present a mathematical analysis of SPCMDPs, showing that although SPC MDPs generally have no optimal policies, every instance of this class has an epsilon-optimal randomized policy for any > 0. We propose a dynamic programming-based algorithm for finding such policies, and empirically demonstrate this algorithm to be orders of magnitude faster than its next-best alternative.
A Simple Polynomial-Time Randomized Distributed Algorithm for Connected Row Convex Constraints
Authors: Kumar T. K. Satish , Nguyen Duc Thien , Yeoh William , Koenig Sven
Published: June 2022

In this paper, we describe a simple randomized algorithm that runs in polynomial time and solves connected row convex (CRC) constraints in distributed settings. CRC constraints generalize many known tractable classes of constraints like 2-SAT and implicational constraints. They can model problems in many domains including temporal reasoning and geometric reasoning, and generally speaking, play the role of ``Gaussians'' in the logical world. Our simple randomized algorithm for solving them in distributed settings, therefore, has a number of important applications. We support our claims through a theoretical analysis and empirical results.
A Scheduler for Actions with Iterated Durations
Authors: Paterson James , Timmons Eric , Williams Brian
Published: June 2022

A wide range of robotic missions contain actions that exhibit looping behavior. Examples of these actions include picking fruit in agriculture, pick-and-place tasks in manufacturing and search patterns in robotic search or survey missions. These looping actions often have a range of acceptable values for the number of loops and a preference function over them. For example, during robotic survey missions, the information gain is expected to increase with the number of loops in a search pattern. Since these looping actions also take time, which is typically bounded, there is a challenge of maximizing utility while respecting time constraints. In this paper, we introduce the Looping Temporal Problem with Preference (LTPP) as a simple parameterized extension of a simple temporal problem. In addition, we introduce a scheduling algorithm for LTPPs which leverages the structure of the problem to find the optimal solution efficiently. We show more than an order of magnitude improvement in run-time over current scheduling techniques and framing a LTPP as a MINLP.
Computing Contingent Plans via Fully Observable Non-Deterministic Planning
Authors: Muise Christian , Belle Vaishak , McIlraith Sheila
Published: June 2022

Planning with sensing actions under partial observability is a computationally challenging problem that is fundamental to the realization of AI tasks in areas as diverse as robotics, game playing, and diagnostic problem solving. Recent work on generating plans for partially observable domains has advocated for online planning, claiming that offline plans are often too large to generate. Here we push the envelope on this challenging problem, proposing a technique for generating conditional (aka contingent) plans offline. The key to our planner's success is the reliance on state-of-the-art techniques for fully observable non-deterministic (FOND) planning. In particular, we use an existing compilation for converting a planning problem under partial observability and sensing to a FOND planning problem. With a modified FOND planner in hand, we are able to scale beyond previous techniques for generating conditional plans with solutions that are orders of magnitude smaller than previously possible in some domains.
GP-Localize: Persistent Mobile Robot Localization Using Online Sparse Gaussian Process Observation Model
Authors: Xu Nuo , Low Kian Hsiang , Chen Jie , Lim Keng Kiat , Ozgul Etkin
Published: June 2022

Central to robot exploration and mapping is the task of persistent localization in environmental fields characterized by spatially correlated measurements. This paper presents a Gaussian process localization (GP-Localize) algorithm that, in contrast to existing works, can exploit the spatially correlated field measurements taken during a robot's exploration (instead of relying on prior training data) for efficiently and scalably learning the GP observation model online through our proposed novel online sparse GP. As a result, GP-Localize is capable of achieving constant time and memory (i.e., independent of the size of the data) per filtering step, which demonstrates the practical feasibility of using GPs for persistent robot localization and autonomy. Empirical evaluation via simulated experiments with real-world datasets and a real robot experiment shows that GP-Localize outperforms existing GP localization algorithms.
Generalizing Policy Advice with Gaussian Process Bandits for Dynamic Skill Improvement
Authors: Glover Jared , Zhu Charlotte
Published: June 2022

We present a ping-pong-playing robot that learns to improve its swings with human advice. Our method learns a reward function over the joint space of task and policy parameters T×P, so the robot can explore policy space more intelligently in a way that trades off exploration vs. exploitation to maximize the total cumulative reward over time. Multimodal stochastic polices can also easily be learned with this approach when the reward function is multimodal in the policy parameters. We extend the recently-developed Gaussian Process Bandit Optimization framework to include exploration-bias advice from human domain experts, using a novel algorithm called Exploration Bias with Directional Advice (EBDA).
Explanation-Based Approximate Weighted Model Counting for Probabilistic Logics
Authors: Renkens Joris , Kimmig Angelika , Van den Broeck Guy , De Raedt Luc
Published: June 2022

Probabilistic inference can be realized using weighted model counting. Despite a lot of progress, computing weighted model counts exactly is still infeasible for many problems of interest, and one typically has to resort to approximation methods. We contribute a new bounded approximation method for weighted model counting based on probabilistic logic programming principles. Our bounded approximation algorithm is an anytime algorithm that provides lower and upper bounds on the weighted model count. An empirical evaluation on probabilistic logic programs shows that our approach is effective in many cases that are currently beyond the reach of exact methods.
Approximate Lifting Techniques for Belief Propagation
Authors: Singla Parag , Nath Aniruddh , Domingos Pedro
Published: June 2022

Many AI applications need to explicitly represent relational structure as well as handle uncertainty. First order probabilistic models combine the power of logic and probability to deal with such domains. A naive approach to inference in these models is to propositionalize the whole theory and carry out the inference on the ground network. Lifted inference techniques (such as lifted belief propagation; Singla and Domingos 2008) provide a more scalable approach to inference by combining together groups of objects which behave identically. In many cases, constructing the lifted network can itself be quite costly. In addition, the exact lifted network is often very close in size to the fully propositionalized model. To overcome these problems, we present approximate lifted inference, which groups together similar but distinguishable objects and treats them as if they were identical. Early stopping terminates the execution of the lifted network construction at an early stage resulting in a coarser network. Noise-tolerant hypercubes allow for marginal errors in the representation of the lifted network itself. Both of our algorithms can significantly speed up the process of lifted network construction as well as result in much smaller models. The coarseness of the approximation can be adjusted depending on the accuracy required, and we can bound the resulting error. Extensive evaluation on six domains demonstrates great efficiency gains with only minor (or no) loss in accuracy.
Point-Based POMDP Solving with Factored Value Function Approximation
Authors: Veiga Tiago , Spaan Matthijs , Lima Pedro
Published: June 2022

Partially observable Markov decision processes (POMDPs) provide a principled mathematical framework for modeling autonomous decision-making problems. A POMDP solution is often represented by a value function comprised of a set of vectors. In the case of factored models, the size of these vectors grows exponentially with the number of state factors, leading to scalability issues. We consider an approximate value function representation based on a linear combination of basis functions. In particular, we present a backup operator that can be used in any point-based POMDP solver. Furthermore, we show how under certain conditions independence between observation factors can be exploited for large computational gains. We experimentally verify our contributions and show that they have the potential to improve point-based methods in policy quality and solution size.
Advice Provision for Choice Selection Processes with Ranked Options
Authors: Azaria Amos , Gal Ya'akov , Goldman Claudia , Kraus Sarit
Published: June 2022

Choice selection processes are a family of bilateral games of incomplete information in which a computer agent generates advice for a human user while considering the effect of the advice on the user's behavior in future interactions. The human and the agent may share certain goals, but are essentially self-interested. This paper extends selection processes to settings in which the actions available to the human are ordered and thus the user may be influenced by the advice even though he doesn't necessarily follow it exactly. In this work we also consider the case in which the user obtains some observation on the sate of the world. We propose several approaches to model human decision making in such settings. We incorporate these models into two optimization techniques for the agent advice provision strategy. In the first one the agent used a social utility approach which considered the benefits and costs for both agent and person when making suggestions. In the second approach we simplified the human model in order to allow modeling and solving the agent strategy as an MDP. In an empirical evaluation involving human users on AMT, we showed that the social utility approach significantly outperformed the MDP approach.
Content-Structural Relation Inference in Knowledge Base
Authors: Zhao Zeya , Jia Yantao , Wang Yuanzhuo
Published: June 2022

Relation inference between concepts in knowledge base has been extensively studied in recent years. Previous methods mostly apply the relations in the knowledge base, without fully utilizing the contents, i.e., the attributes of concepts in knowledge base. In this paper, we propose a content-structural relation inference method (CSRI) which integrates the content and structural information between concepts for relation inference. Experiments on data sets show that CSRI obtains 15% improvement compared with the state-of-the-art methods.
Partial Satisfaction Planning under Time Uncertainty with Control on When Objectives Can Be Aborted
Authors: Labranche Sylvain , Beaudry Éric
Published: June 2022

In real world planning problems, it might not be possible for an automated agent to satisfy all the objectives assigned to it because available resources are limited. When objectives cannot all be satisfied, classical planning returns no plan. In partial satisfaction planning, it is possible to satisfy only a subset of the objectives. To solve this kind of problems, an agent could select the objectives subset and the plan that maximizes the net benefit, i.e. the sum of satisfied objectives utilities minus the sum of the cost of actions. This approach has been experimented for deterministic planning. This paper extends partial satisfaction planning for problems with uncertainty on time. For problems under uncertainty, the best subset of objectives may not be calculated at planning time. The effective duration of actions at execution time may dynamically influence the achievable subset of objectives. Our approach introduces special actions to explicitly abort objectives. This enables control on when an objective is aborted.
A Model for Aggregating Contributions of Synergistic Crowdsourcing Workflows
Authors: Fang Yili , Sun Hailong , Zhang Richong , Huai Jinpeng , Mao Yongyi
Published: June 2022

One of the most important crowdsourcing topics is to study the effective quality control methods so as to reduce the cost and to guarantee the quality of task processing. As an effective approach, iterative improvement workflow is known to choose the best result from multiple workflows. However, for complex crowdsourcing tasks that consists of a certain number of subtasks under some specific constraints, but cannot be split into subtasks to be crowdsourced, the approach merely considers the best workflow without integrating the contributions of all workflows, which potentially results in extra costs for more iterations. In this paper, we propose an assembly model to integrate the best output of subtasks from different workflows. Moreover, we devise an efficient iterative method based on POMDP to improve the quality of assembled output. Empirical studies confirms the superiority of our proposed model.
A Novel Single-DBN Generative Model for Optimizing POMDP Controllers by Probabilistic Inference
Authors: Kiselev Igor , Poupart Pascal
Published: June 2022

As a promising alternative to using standard (often intractable) planning techniques with Bellman equations, we propose an interesting method of optimizing POMDP controllers by probabilistic inference in a novel equivalent single-DBN generative model. Our inference approach to POMDP planning allows for (1) for application of various techniques for probabilistic inference in single graphical models, and (2) for exploiting the factored structure in a controller architecture to take advantage of natural structural constrains of planning problems and represent them compactly. Our contributions can be summarized as follows: (1) we designed a novel single-DBN generative model that ensures that the task of probabilistic inference is equivalent to the original problem of optimizing POMDP controllers, and (2) we developed several inference approaches to approximate the value of the policy when exact inference methods are not tractable to solve large-size problems with complex graphical models. The proposed approaches to policy optimization by probabilistic inference are evaluated on several POMDP benchmark problems and the performance of the implemented approximation algorithms is compared.
Social Capital in Network Organizations
Authors: Alqithami Saad , Hexmoor Henry
Published: June 2022

In a dynamic network organization, member agents usually interact to coordinate their actions and to cooperate towards a common goal with which they have no previous experience. These relations allow them to produce a cohesive group to build and maintain their network. This paper will outline the effect of social capital on a network structure inside a network organization.
Backdoors into Heterogeneous Classes of SAT and CSP
Authors: Gaspers Serge , Misra Neeldhara , Ordyniak Sebastian , Szeider Stefan , Zivny Stanislav
Published: June 2022

Backdoor sets represent clever reasoning shortcuts through the search space for SAT and CSP. By instantiating the backdoor variables one reduces the given instance to several easy instances that belong to a tractable class.The overall time needed to solve the instance is exponential in the size of the backdoor set, hence it is a challenging problem to find a small backdoor set if one exists; over the last years this problem has been subject of intensive research. In this paper we extend the classical notion of a strong backdoor set by allowing that different instantiations of the backdoor variables result in instances that belong to different base classes; the union of the base classes forms a heterogeneous base class. Backdoor sets to heterogeneous base classes can be much smaller than backdoor sets to homogeneous ones, hence they are much more desirable but possibly harder to find. We draw a detailed complexity landscape for the problem of detecting strong backdoor sets into heterogeneous base classes for SAT and CSP. We provide algorithms that establish fixed-parameter tractability under natural parameterizations, and we contrast the tractability results with hardness results that pinpoint the theoretical limits. Our results apply to the current state-of-the-art of tractable classes of CSP and SAT that are definable by restricting the constraint language.
Fast Consistency Checking of Very Large Real-World RCC-8 Constraint Networks Using Graph Partitioning
Authors: Nikolaou Charalampos , Koubarakis Manolis
Published: June 2022

We present a new reasoner for RCC-8 constraint networks, called gp-rcc8, that is based on the patchwork property of path-consistent tractable RCC-8 networks and graph partitioning. We compare gp-rcc8 with state of the art reasoners that are based on constraint propagation and backtracking search as well as one that is based on graph partitioning and SAT solving. Our evaluation considers very large real-world RCC-8 networks and medium-sized synthetic ones, and shows that gp-rcc8 outperforms the other reasoners for these networks, while it is less efficient for smaller networks.
Q-Intersection Algorithms for Constraint-Based Robust Parameter Estimation
Authors: Carbonnel Clement , Trombettoni Gilles , Vismara Philippe , Chabert Gilles
Published: June 2022

Given a set of axis-parallel n-dimensional boxes, the q-intersection is defined as the smallest box encompassing all the points that belong to at least q boxes. Computing the q-intersection is a combinatorial problem that allows us to handle robust parameter estimation with a numerical constraint programming approach. The q-intersection can be viewed as a filtering operator for soft constraints that model measurements subject to outliers. This paper highlights the equivalence of this operator with the search of q-cliques in a graph whose boxicity is bounded by the number of variables in the constraint network. We present a computational study of the q-intersection. We also propose a fast heuristic and a sophisticated exact q-intersection algorithm. First experiments show that our exact algorithm outperforms the existing one while our heuristic performs an efficient filtering on hard problems.
A Support-Based Algorithm for the Bi-Objective Pareto Constraint
Authors: Hartert Renaud , Schaus Pierre
Published: June 2022

Bi-Objective Combinatorial Optimization problems are ubiquitous in real-world applications and designing approaches to solve them efficiently is an important research area of Artificial Intelligence. In Constraint Programming, the recently introduced bi-objective Pareto constraint allows one to solve bi-objective combinatorial optimization problems exactly. Using this constraint, every non-dominated solution is collected in a single tree-search while pruning sub-trees that cannot lead to a non-dominated solution. This paper introduces a simpler and more efficient filtering algorithm for the bi-objective Pareto constraint. The efficiency of this algorithm is experimentally confirmed on classical bi-objective benchmarks.
Towards Topological-Transformation Robust Shape Comparison: A Sparse Representation Based Manifold Embedding Approach
Authors: Gao Longwen , Zhou Shuigeng
Published: June 2022

Non-rigid shape comparison based on manifold embeddingusing Generalized Multidimensional Scaling(GMDS) has attracted much attention for its highaccuracy. However, this method requires that shape surfaceis not elastic. In other words, it is sensitive totopological transformations such as stretching and compressing.To tackle this problem, we propose a new approachthat constructs a high-dimensional space to embedthe manifolds of shapes based on sparse representation,which is able to completely withstand rigid transformationsand considerably tolerate topological transformations.Experiments on TOSCA shapes validate theproposed approach.
Efficient Object Detection via Adaptive Online Selection of Sensor-Array Elements
Authors: Philipose Matthai
Published: June 2022

We examine how to use emerging far-infrared imager ensembles to detect certain objects of interest (e.g., faces, hands, people and animals) in synchronized RGB video streams at very low power. We formulate the problem as one of selecting subsets of sensing elements (among many thousand possibilities) from the ensembles for tests. The subset selection problem is naturally adaptive and online: testing certain elements early can obviate the need for testing many others later, and selection policies must be updated at inference time. We pose the ensemble sensor selection problem as a structured extension of test-cost-sensitive classification, propose a principled suite of techniques to exploit ensemble structure to speed up processing and show how to re-estimate policies fast. We estimate reductions in power consumption of roughly 50x relative to even highly optimized implementations of face detection, a canonical object-detection problem. We also illustrate the benefits of adaptivity and online estimation.
A Schedule Optimization Tool for Destructive and Non-Destructive Vehicle Tests
Authors: Ludwig Jeremy , Kalton Annaka , Richards Robert , Bautsch Brian , Markusic Craig , Schumacher J.
Published: June 2022

Whenever an auto manufacturer refreshes an existing car or truck model or builds a new one, the model will undergo hundreds if not thousands of tests before the factory line and tooling is finished and vehicle production beings. These tests are generally carried out on expensive, custom-made vehicles because the new factory lines for the model do not exist yet. The work presented in this paper describes how an existing intelligent scheduling software framework was modified to include domain-specific heuristics used in the vehicle test planning process. The result of this work is a prototype scheduling tool that optimizes the overall given test schedule in order to complete the work in a given time window while minimizing the total number of vehicles required for the test schedule. Initial results are presented that show a reduction in required test vehicles compared to manual scheduling of the same tasks as well as increased capability to ask “what-if” questions to further improve the schedule.
Retweet Behavior Prediction Using Hierarchical Dirichlet Process
Authors: Zhang Qi , Gong Yeyun , Guo Ya , Huang Xuanjing
Published: June 2022

The task of predicting retweet behavior is an important and essential step for various social network applications, such as business intelligence, popular event prediction, and so on. Due to the increasing requirements, in recent years, the task has attracted extensive attentions. In this work, we propose a novel method using non-parametric statistical models to combine structural, textual, and temporal information together to predict retweet behavior. To evaluate the proposed method, we collect a large number of microblogs and their corresponding social networks from a real microblog service. Experimental results on the constructed dataset demonstrate that the proposed method can achieve better performance than state-of-the-art methods. The relative improvement of the the proposed over the method using only textual information is more than 38.5% in terms of F1-Score.
RAIN: Social Role-Aware Information Diffusion
Authors: Yang Yang , Tang Jie , Leung Cane , Sun Yizhou , Chen Qicong , Li Juanzi , Yang Qiang
Published: June 2022

Information diffusion, which studies how information is propagated in social networks, has attracted considerable research effort recently. However, most existing approaches do not distinguish social roles that nodes may play in the diffusion process. In this paper, we study the interplay between users' social roles and their influence on information diffusion. We propose a Role-Aware INformation diffusion model (RAIN) that integrates social role recognition and diffusion modeling into a unified framework. We develop a Gibbs-sampling based algorithm to learn the proposed model using historical diffusion data. The proposed model can be applied to different scenarios. For instance, at the micro-level, the proposed model can be used to predict whether an individual user will repost a specific message; while at the macro-level, we can use the model to predict the scale and the duration of a diffusion process. We evaluate the proposed model on a real social media data set. Our model performs much better in both micro- and macro-level prediction than several alternative methods.
Inferring Same-As Facts from Linked Data: An Iterative Import-by-Query Approach
Authors: Al-Bakri Mustafa , Atencia Manuel , Lalande Steffen , Rousset Marie-Christine
Published: June 2022

In this paper we model the problem of data linkage in Linked Data as a reasoning problem on possibly decentralized data. We describe a novel import-by-query algorithm that alternates steps of sub-query rewriting and of tailored querying the Linked Data cloud in order to import data as specific as possible for inferring or contradicting given target same-as facts. Experiments conducted on a real-world dataset have demonstrated the feasibility of this approach and its usefulness in practice for data linkage and disambiguation.
Consistent Knowledge Discovery from Evolving Ontologies
Authors: Lecue Freddy , Pan Jeff
Published: June 2022

Deductive reasoning and inductive learning are the most common approaches for deriving knowledge. In real world applications when data is dynamic and incomplete, especially those exposed by sensors, reasoning is limited by dynamics of data while learning is biased by data incompleteness. Therefore discovering consistent knowledge from incomplete and dynamic data is a challenging open problem. In our approach the semantics of data is captured through ontologies to empower learning (mining) with (Description Logics) reasoning. Consistent knowledge discovery is achieved by applying generic, significative, representative association semantic rules. The experiments have shown scalable, accurate and consistent knowledge discovery with data from Dublin.
Extracting Bounded-Level Modules from Deductive RDF Triplestores
Authors: Rousset Marie-Christine , Ulliana Federico
Published: June 2022

We present a novel semantics for extracting bounded-level modules from RDF ontologies and databases augmented with safe inference rules, a la Datalog. Dealing with a recursive rule language poses challenging issues for defining the module semantics, and also makes module extraction algorithmically unsolvable in some cases. Our results include a set of module extraction algorithms compliant with the novel semantics. Experimental results show that the resulting framework is effective in extracting expressive modules from RDF datasets with formal guarantees, whilst controlling their succinctness.